package puzzle.projecteuler.p300;

import java.math.BigInteger;
import java.util.HashSet;
import java.util.Set;

public class Problem206B {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		Set<String> as = candidates("5?6?7?8?9?0");
		for (String a : as) {
			char[] r = (new BigInteger(a)).pow(2).toString().toCharArray();
			if (r.length == 19 && r[0]=='1' && r[2]=='2' && r[4]=='3' && r[6]=='4') {
				System.out.println(a);
			}
		}
	}

	/**
	 * 
	 * @param s
	 * @param pattern "1?2?3?4?5?6?7?8?9?0"
	 * @return
	 */
	private static Set<String> candidates(String pattern) {
	
		if (pattern.length() == 1) {
			Set<String> s = new HashSet<String>();
			for (int i = 0; i < 10; i ++) {
				char r = (char)('0' + (i*i)%10);
				if (pattern.charAt(0) == '?' || pattern.charAt(0) == r) {
					s.add(BigInteger.valueOf(i).toString());
				}
			}
			return s;
		} else {
			String newPattern = pattern.substring(1, pattern.length());
			Set<String> t = candidates(newPattern);
			Set<String> s = new HashSet<String>();
			for (int i = 0; i < 10; i ++) {
				for (String b: t) {
					BigInteger a = new BigInteger(i + b);
					String r = a.pow(2).toString();
					char c = '0';
					if (r.length()>=pattern.length()) {
						c = r.charAt(r.length()-pattern.length());
					}
					if (pattern.charAt(0) == '?' || pattern.charAt(0) == c) {
						String tmp = a.toString();
						while (tmp.length() < pattern.length()) {
							tmp = "0" + tmp;
						}
						s.add(tmp);
					}
				}
			}
			return s;
		}
	}
}
